package algorithm.leetcode.medium;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2021/1/4
 */
public class Question306 {

    public static void main(String[] args) {
        String num = "112358";
        Question306 question = new Question306();
        boolean flg = question.isAdditiveNumber(num);
        System.out.println(flg);
    }

    public boolean isAdditiveNumber(String num) {
        return dfs(num, num.length(), 0, 0, 0, 0);
    }

    /**
     *
     * @param num 原始字符串
     * @param len 原始字符串长度
     * @param idx 当前处理下标
     * @param sum 前两个数字之和
     * @param pre 前一个数字
     * @param k 当前是处理的第几个数字
     */
    private boolean dfs(String num, int len, int idx, long sum, long pre, int k) {
        if (idx == len) {
            return k > 2;
        }

        for (int i = idx; i < len; i++) {
            long cur = fetchCurValue(num, idx, i);
            if (cur < 0) {
                continue;
            }
            // 当前数字不等于前两个数字之和
            if (k >= 2 && cur != sum) {
                continue;
            }
            if (dfs(num, len, i + 1, pre + cur, cur, k + 1)) {
                return true;
            }
        }
        return false;
    }

    private long fetchCurValue(String num, int l, int r) {
        if (l < r && num.charAt(l) == '0') {
            return -1;
        }
        long res = 0;
        while (l <= r) {
            // 构造
            res = res * 10 + num.charAt(l++) - '0';
        }
        return res;
    }


}
